package sort;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {

    @Test
    public void testAddAndPoll() {
        int capacity = 16;
        Heap h = new Heap(capacity);
        Random r = new Random();
        int[] array = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            int n = r.nextInt(100);
            array[i] = n;
            h.add(n);
            System.out.format("added: %d, top: %d, array: %s\n", n, h.peek(), Arrays.toString(array));
        }
        sort(array);
    }

    @Test
    public void testSort() {
        sort(1);
        sort(1, 2);
        sort(2, 1);
        sort(1, 2, 3);
        sort(1, 3, 2);
        sort(2, 1, 3);
        sort(2, 3, 1);
        sort(3, 1, 2);
        sort(3, 2, 1);
        sort(1, 2, 3, 4);
        sort(1, 2, 4, 3);
        sort(1, 3, 2, 4);
        sort(1, 3, 4, 2);
        sort(1, 4, 2, 3);
        sort(1, 4, 3, 2);
        sort(2, 1, 3, 4);
        sort(2, 1, 4, 3);
        sort(2, 3, 1, 4);
        sort(2, 3, 4, 1);
        sort(2, 4, 1, 3);
        sort(2, 4, 3, 1);
        sort(3, 1, 2, 4);
        sort(3, 1, 4, 2);
        sort(3, 2, 1, 4);
        sort(3, 2, 4, 1);
        sort(3, 4, 1, 2);
        sort(3, 4, 2, 1);
        sort(4, 1, 2, 3);
        sort(4, 1, 3, 2);
        sort(4, 2, 1, 3);
        sort(4, 2, 3, 1);
        sort(4, 3, 1, 2);
        sort(4, 3, 2, 1);
    }
    
    public static void sort(int... array) {
        Heap h = new Heap(array);
        int[] sorted = new int[h.size];
        for (int i = 0; i < sorted.length; i++) {
            sorted[i] = h.poll();
        }
        System.out.println(Arrays.toString(sorted));
    }
    

    public static class Heap {
        int[] array;
        public int size;

        public Heap(int capacity) {
            this.array = new int[capacity];
            this.size = 0;
        }

        public Heap(int... array) {
            this.array = array;
            this.size = array.length;
            adjust();
        }

        // get the top
        public int peek() {
            if (this.size > 0) {
                return this.array[0];
            }
            return Integer.MIN_VALUE;
        }

        // get and remove the top
        public int poll() {
            if (this.size > 0) {
                int top = this.array[0];
                if (this.size > 1) {
                    this.array[0] = this.array[size-1];
                }
                size--;
                // KEYNOTE: NOT adjust(), only heapify()
                heapify(0);
                return top;
            }
            return Integer.MIN_VALUE;
        }

        public boolean add(int element) {
            if (this.size < this.array.length) {
                this.array[this.size] = element;
                this.size++;
                // KEYNOTE: NOT adjust(), NOT heapify(), but only compare with parent recursively
                int childIndex = this.size - 1;
                while (childIndex > 0) {
                    int parentIndex = parentIndex(childIndex);
                    if (this.array[parentIndex] < this.array[childIndex]) {
                        swap(parentIndex, childIndex);
                    }
                    childIndex = parentIndex;
                }
                return true;
            }
            return false;
        }

        private void adjust() {
            for (int i = this.size/2; i >= 0; i--) {
                heapify(i);
            }
        }

        private void heapify(int parentIndex) {
            int leftIndex = leftIndex(parentIndex);
            int rightIndex = rightIndex(parentIndex);

            /* KEYNOTE: NOT the most optimal, because heapify twice
            if (rightIndex < this.size) {
                if (array[rightIndex] < array[parentIndex]) {
                    swap(rightIndex, parentIndex);
                    heapify(rightIndex);
                }
            }
            if (leftIndex < this.size) {
                if (array[leftIndex] < array[parentIndex]) {
                    swap(leftIndex, parentIndex);
                    heapify(leftIndex);
                }
            }
            */

            // blow only heapify once
            int smallestIndex = parentIndex;
            if (rightIndex < this.size && array[rightIndex] < array[smallestIndex]) {
                smallestIndex = rightIndex;
            }

            if (leftIndex < this.size && array[leftIndex] < array[smallestIndex]) {
                smallestIndex = leftIndex;
            }

            if (smallestIndex != parentIndex) {
                swap(smallestIndex, parentIndex);
                heapify(smallestIndex);
            }
        }

        private static int leftIndex(int parentIndex) {
            return (parentIndex << 1) + 1;
        }

        private static int rightIndex(int parentIndex) {
            return (parentIndex << 1) + 2;
        }

        private static int parentIndex(int childIndex) {
            return (childIndex - 1) >> 1;
        }

        private void swap(int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}
